package problems.daily;

import java.util.ArrayList;
import java.util.List;

/**
 * 1177.构建回文串检测
 * <p></p>
 * @author dubulingbo, 2023/6/15 11:24.
 */
public class DT1177 {
    // 位运算 - 异或前缀和
    public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
        int n = s.length();
        // 统计每个小写字母异或前缀和
        // 奇数 -> 1
        // 偶数 -> 0
        // 刚好用来表示奇偶性，最后统计奇数有多少个，即统计整数的 bit 中有多少个 1
        int[] ps = new int[n + 1];

        for (int i = 0; i < n; ++i) {
            ps[i + 1] = ps[i] ^ (1 << (s.charAt(i) - 'a'));
        }

        List<Boolean> ans = new ArrayList<>();
        for (int[] q : queries) {
            int oddCnt = Integer.bitCount(ps[q[1] + 1] ^ ps[q[0]]);
            // 只需统计数量为奇数的字母种类数即可，
            // 最小需要替换的字母数就是 oddCnt / 2（整除）
            ans.add(q[2] >= (oddCnt >> 1));
        }

        return ans;
    }

    public List<Boolean> canMakePaliQueries1(String s, int[][] queries) {
        int n = s.length();
        final int N = 26;
        // 统计每个小写字母的数量的前缀和数组
        // prefixSum[i][26] 表示字符串 s 在 [0, i) 范围上的各个字母的数量
        int[][] prefixSum = new int[n + 1][N];

        for (int i = 0; i < n; ++i) {
            System.arraycopy(prefixSum[i], 0, prefixSum[i + 1], 0, N);
            ++prefixSum[i + 1][s.charAt(i) - 'a'];
        }

        List<Boolean> ans = new ArrayList<>();
        for (int[] q : queries) {
            int oddCnt = 0;
            int left = q[0], right = q[1] + 1;

            for (int i = 0; i < N; ++i) {
                if (((prefixSum[right][i] - prefixSum[left][i]) & 1) != 0) {
                    ++oddCnt;
                }
            }

            // 只需统计数量为奇数的字母种类数即可，
            // 最小需要替换的字母数就是 oddCnt / 2（整除）
            ans.add(q[2] >= oddCnt / 2);
        }

        return ans;
    }
}
